package Sequence;

import java.util.Arrays;

public class Test0516 {
    public static void main(String[] args) {
        System.out.println(new Solution0516_1().longestPalindromeSubseq("bbbab"));
    }
}

class Solution0516_1 {
    public int longestPalindromeSubseq(String s) {
        char[] charArray = s.toCharArray();
        int length = charArray.length;
        int[] dp1 = new int[length+1];
        int[] dp2 = new int[length+1];

        int ans = 1;
        for (int i = 0; i < length; i++) {
            dp2[i]=1;

            for (int j = i - 1; j >= 0; j--) {
                if (charArray[i] == charArray[j]){
                    dp2[j]= (j+1==i?0:dp1[j+1])+2;
                }else {
                    dp2[j]=Math.max(j+1==i?1:dp2[j+1],dp1[j]);
                }

                ans = Math.max(ans,dp2[j]);
            }

            int[] temp = dp1;
            dp1 = dp2;
            dp2 = temp;
        }

        return ans;
    }
}